package com.chenhao.springcloud.chenhaodatastructureservice.sort;

import org.bouncycastle.util.Arrays;

/**
 * Description:插入排序(有序数组的时间复杂度O（n^2）)
 *
 * @author chenhao
 * @date 2020/12/4 11:48
 */
public class InsertionSort {
    private InsertionSort(){}

    public static  <E extends Comparable<E>> void sort(E[] arr){
        for (int i=0; i<arr.length;i++){
            for (int j= i;j-1>=0;j--){
                if (arr[j].compareTo(arr[j-1])<0){
                    swap(arr,j,j-1);
                }else {
                    break;
                }
            }
        }
    }

    /**
     * 优化
     * @param arr
     * @param <E>
     */
    public static  <E extends Comparable<E>> void sort2(E[] arr){
        for (int i=0;i< arr.length;i++){
            E t = arr[i];
            int j;
            for (j=i;i-1>=0&&t.compareTo(arr[j-1])<0;j--){
                arr[j] = arr[j-1];
            }
            arr[j] = t;
        }
    }
    /**
     * 交换数据
     * @param arr
     * @param i
     * @param j
     */
    private static <E> void swap(E[] arr,int i,int j){
        E t = arr[i];
        arr[i] =arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int [] dataSize = {1000,100000};
        for (int n :dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArry(n,n);
            SortingHelper.sortTest("InsertionSort",arr);
            SortingHelper.sortTest("InsertionSort2",arr);
        }

    }
}
